// 方案二：原地更新
// 时间复杂度：O(mn)
// 空间复杂度：O(1)
func gameOfLife(board [][]int)  {
    directions := [][]int{
        {-1, 0}, {1, 0}, {0, -1}, {0, 1},
        {-1, -1}, {-1, 1}, {1, -1}, {1, 1},
    }
    m := len(board)
    n := len(board[0])

    // 遍历每个细胞，并确定它最终的状态
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            // 对于每一个细胞统计其八个相邻位置里的活细胞数量
            liveNeighbors := 0
            for _, dir := range directions {
                nextRow := i + dir[0]
                nextCol := j + dir[1]
                if nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n {
                    if math.Abs(float64(board[nextRow][nextCol])) == 1 {
                        liveNeighbors++
                    }
                }
            }
            // 1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
            if board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3) {
                board[i][j] = -1
            }

            // 2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；

            // 3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；

            // 4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
            if board[i][j] == 0 && liveNeighbors == 3 {
                board[i][j] = 2
            }
        }
    }

    // 遍历 board 得到一次更新后的状态
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] > 0 {
                board[i][j] = 1
            } else {
                board[i][j] = 0
            }
        }
    }
}

// 方案一：使用辅助数组
// 时间复杂度：O(mn)
// 空间复杂度：O(mn)
func gameOfLife1(board [][]int)  {
    directions := [][]int{
        {-1, 0}, {1, 0}, {0, -1}, {0, 1},
        {-1, -1}, {-1, 1}, {1, -1}, {1, 1},
    }
    m := len(board)
    n := len(board[0])
    // 创建复制数组 copyBoard
    copyBoard := make([][]int, m)
    for i := range copyBoard {
        copyBoard[i] = make([]int, n)
    }

    // 从原数组复制一份到 copyBoard 中
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            copyBoard[i][j] = board[i][j]
        }
    }

    // 遍历每个细胞，并确定它最终的状态
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            // 对于每一个细胞统计其八个相邻位置里的活细胞数量
            liveNeighbors := 0
            for _, dir := range directions {
                nextRow := i + dir[0]
                nextCol := j + dir[1]
                if nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && copyBoard[nextRow][nextCol] == 1 {
                    liveNeighbors++
                }
            }
            // 1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
            if copyBoard[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3) {
                board[i][j] = 0
            }

            // 2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；

            // 3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；

            // 4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
            if copyBoard[i][j] == 0 && liveNeighbors == 3 {
                board[i][j] = 1
            }

        }
    }
}